package com.yulongtian.weekCompetition.month202302.week02;

import java.util.Stack;

/**
 * https://leetcode.cn/problems/subsequence-with-the-minimum-score/
 *
 * @author yulongTian
 * @create 2023-02-13 14:18
 */
public class Test04 {
    public static void main(String[] args) {
        System.out.println(minimumScore("abacaba", "bzaa"));
    }

    /**
     * 维护两个指针: i 和 j。
     * 我们需要执行一个类似的操作: 当 t [0: i ] + t [ j: n ]不是字符串 s 的子序列时，增加 j。
     * <p>
     * 我们可以贪婪地检查病情。创建表示最小索引 k 的数组 left most [ i ] ，
     * 使前缀 s [0: k ]中存在子序列 t [0: i ]。类似地，我们定义最右[ i ]。
     * <p>
     * 如果最左[ i ] < 最右[ j ] ，则 t [0: i ] + t [ j: n ]是 s 的子序列。
     *
     * @param s
     * @param t
     * @return
     */
    /*
    O(n)的做法：用一个栈，
    先从右往左匹配一次，
    把匹配到的s串的位置压栈；
    再从左往右匹配一次，每匹配到一个就弹栈，
    直到栈顶的位置大于当前s串的位置，更新答案。
     */
    public static int minimumScore(String s, String t) {
        //栈
        Stack<Integer> stack = new Stack<>();

        //从右往左匹配
        int s_n = s.length(), t_n = t.length();
        for (int i = s_n - 1, j = t_n - 1; i >= 0 && j >= 0; i--) {
            if (s.charAt(i) == t.charAt(j)) {
                stack.push(i);
                j--;
            }
        }
        int ans = t_n - stack.size();
        //从左往右匹配
        for (int i = 0, j = 0; i < s_n && j < t_n; i++) {
            if (s.charAt(i) == t.charAt(j)) {
                while (!stack.empty() && stack.peek() <= i) {
                    stack.pop();
                }
                ++j;
            }
            ans = Math.max(0, Math.min(ans, t_n - j - stack.size()));
        }
        return ans;
    }


}
